/**
 * https://leetcode-cn.com/problems/minimum-window-substring/solution/leetcode-76-zui-xiao-fu-gai-zi-chuan-cja-lmqz/
*/

#include <string>
#include <unordered_map>
using namespace std;
class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char,int> hs,ht;
        for(auto c : t) ht[c]++;
        string res;
        int cnt = 0;
        for(int i = 0,j = 0; i < s.size(); ++i){
            hs[s[i]] ++;
            if(hs[s[i]] <= ht[s[i]]) cnt ++;
            while(hs[s[j]] > ht[s[j]]) hs[s[j++]] --; // 收缩滑动窗口
            if(cnt == t.size()){
                if(res.empty() || i - j + 1 < res.size())
                    res = s.substr(j,i - j + 1);
            }
        }
        return res;
    }
};
int main()
{
    string s = "ADOBECODEBANC";
    string t = "ABC";
    Solution sol;
    sol.minWindow(s,t);
}